199. 二叉树的右视图

#leetcode/tree/traversal/linear

199. 二叉树的右视图

Similar Question

leading to the advanced question

Solution Tips

方案一: DFS

依赖 depth 处理每次层, 取最后一个节点即可

var rightSideView = function (root) {
    const ans = [];
    function dfs(node, depth) {
        if (!node) {
            return;
        }
        if (ans.length === depth) {
            ans.push(node.val);
        }
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
    dfs(root, 0);
    return ans;
};

方案二: BFS

// bfs - 层序遍历
var rightSideView = function (root) {
    const ans = [];
    const queue = [];
    if (root) {
        queue.push(root);
    }
    while (queue.length) {
        const len = queue.length;
        // 一层层的处理，每一层的最后一个节点就是从右边看到的节点
        ans.push(queue[len - 1].val);
        // 按顺序获取下一层的所有节点
        for (let i = 0; i < len; i++) {
            const cur = queue.shift();
            if (cur.left) {
                queue.push(cur.left);
            }
            if (cur.right) {
                queue.push(cur.right);
            }
        }
    }
    return ans;
};

// dfs - 根右左遍历，并记录深度，来判断是否是该深度第一次访问的节点
var rightSideView = function (root) {
    const ans = [];
    function dfs(node, depth) {
        if (!node) {
            return;
        }
        if (ans.length === depth) {
            ans.push(node.val);
        }
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
    dfs(root, 0);
    return ans;
};